package 完全背包

/*
原题链接:
https://leetcode.cn/problems/coin-change-ii/

518. 零钱兑换 II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。

示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：
输入：amount = 10, coins = [10]
输出：1

思路:
本题意思: 从硬币数组中任选硬币, 组成目标值target, 一共有多少种方案? 没有就返回0

需要注意: 例如需要凑成值为5, 在本题中 2,2,1 和 2,1,2 是同一种方案 (求的是组合数)
可以理解为要装满硬币值的容器, 有多少种组合数

一.dp数组含义
  - dp[j]: 装满容量为j的背包, 有dp[j]种组合数

二.递推公式
  - dp[i] += dp[j-coins[j]]

三.初始化
  - dp[0] = 1	装满背包容量为0, 那么就一个硬币都不装, 也是一种方案
  - dp[0]如果初始化为0, 那么后续所有结果递推都是0了

四.遍历顺序

  - for(i=0; i<coins.size; i++){	//先物品 (得到的组合数)
    for(j=coin[i]; j<=amount; j++) {  //后背包

  - for(j=0; j<=amount; i++){ //先背包  (得到的是排列数)
    for(i=0; i<coins.size; i++) { //后物品

四.遍历顺序
  - for(i=0; i<coins.size; i++){ //先物品(得到的是组合数量
    for(j=coin[i]; j<=amount; j++) { //完全背包,需要正序遍历

1.确定dp数组以及下标的含义
  - dp[j]: 凑成总金额j的货币组合数为dp[j]

2.确定递推公式
  - dp[j]就是所有的dp[j-coins[i]]相加
    所以递推公式: dp[j]+=dp[j-coins[i]]

3.dp数组如何初始化
  - 首先dp[0]一定要为1, dp[0]

4.遍历顺序
  - 先遍历物品, 后遍历背包
    for(int i=0; i<coins.size(); i++){
    for(int j=coins[i]; j<=amount; j++) {

假设: coins[0]=1, coins[1]=5   物品0重量1  物品1重量5
那么就是先把1加入计算, 然后再把5加入计算, 得到方法数量只有{1,5}这种情况. 而不会出现{5,1}的情况
*/
func change(amount int, coins []int) int {

	dp := make([]int, amount+1) //1.定义dp数组
	dp[0] = 1                   //2.初始化,0大小的背包, 当然是不装任何东西了, 就是1种方法

	for i := 0; i < len(coins); i++ { //3.先遍历物品
		for j := coins[i]; j <= amount; j++ { //遍历背包
			dp[j] += dp[j-coins[i]] // 推导公式
		}
	}

	return dp[amount]
}
